package com.base.greedy;

import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 517. 超级洗衣机
 *
 * 假设有 n台超级洗衣机放在同一排上。开始的时候，每台洗衣机内可能有一定量的衣服，也可能是空的。
 *
 * 在每一步操作中，你可以选择任意 m (1 <= m <= n) 台洗衣机，与此同时将每台洗衣机的一件衣服送到相邻的一台洗衣机。
 *
 * 给定一个整数数组machines 代表从左至右每台洗衣机中的衣物数量，请给出能让所有洗衣机中剩下的衣物的数量相等的 最少的操作步数 。如果不能使每台洗衣机中衣物的数量相等，则返回 -1 。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/super-washing-machines
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author leon
 * @date 2021年09月29日 14:20
 */
public class FindMinMoves {
    /**
     * 每次将数组中最大值的桶-1，然后最小值的桶+1
     * @param nums
     * @return
     */
    public int findMinMoves(int[] nums){
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum+=nums[i];
        }
        if (sum % nums.length!=0){
            return -1;
        }
        int e = sum/ nums.length;
        int res = 0,ans = 0;
        for (int i = 0; i < nums.length; i++) {
            ans+=nums[i];
            int need  = ans - e*(i+1);
            res = Math.max(res,Math.max(Math.abs(need),nums[i] - e));
        }
        return res;

    }
}
